/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:排序链表.java
 * Date:2021/02/18 14:19:18
 */

package org.bytedance.链表和数;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class 排序链表 {

    public static void main(String[] args) {

        排序链表 instance = new 排序链表();


        ListNode head = new ListNode(4);
        head.next = new ListNode(2, new ListNode(1, new ListNode(3)));

        instance.printList(head);
        ListNode listNode = instance.sortList(head);
        instance.printList(listNode);

        head = new ListNode(4);
        head.next = new ListNode(2, new ListNode(1, new ListNode(3)));

        instance.printList(head);
        ListNode listNode1 = instance.sortListMerge(head);
        instance.printList(listNode1);


        ListNode head2 = new ListNode(-1, new ListNode(5, new ListNode(3,
                new ListNode(4, new ListNode(0)))));

        instance.printList(head2);
        instance.sortList(head2);
        instance.printList(head2);


        System.out.println("----------------");


        head2 = new ListNode(-1, new ListNode(5, new ListNode(3,
                new ListNode(4, new ListNode(0)))));
        instance.printList(head2);
        ListNode listNode2 = instance.sortListMerge(head2);
        instance.printList(listNode2);


    }

    private void printList(ListNode head) {
        ListNode p = head;
        StringBuilder sb = new StringBuilder();
        while (p != null) {
            sb.append(p.value).append(" ");
            p = p.next;
        }
        System.out.println(sb.toString());
        return;
    }

    private static class ListNode {
        int value;
        ListNode next;

        public ListNode(int value) {
            this.value = value;
        }

        public ListNode(int value, ListNode next) {
            this.next = next;
            this.value = value;
        }
    }

    /**
     * 快速排序
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        //采用快排
        quickSort(head, null);
        return head;
    }

    private void quickSort(ListNode head, ListNode end) {
        if (head != end) {
            ListNode partition = partition(head, end);
            quickSort(head, partition);
            quickSort(partition.next, end);
        }
    }

    private ListNode partition(ListNode head, ListNode end) {
        ListNode p1 = head, p2 = head.next;
        while (p2 != end) {
            //大于key值时，p1向前走一步，交换p1和p2的值
            if (p2.value < head.value) {
                p1 = p1.next;
                int tmp = p1.value;
                p1.value = p2.value;
                p2.value = tmp;
            }
            p2 = p2.next;
        }
        if (p1 != head) {
            int temp = p1.value;
            p1.value = head.value;
            head.value = temp;
        }
        return p1;
    }

    /**
     * 归并排序
     *
     * @param head
     * @return
     */
    public ListNode sortListMerge(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode mid = mid(head);
        ListNode right = mid.next;
        mid.next = null;
        return mergeSort(sortListMerge(head), sortListMerge(right));
    }

    private ListNode mergeSort(ListNode left, ListNode right) {
        ListNode p1 = left, p2 = right, head;
        if (p1.value < p2.value) {
            head = left;
            p1 = p1.next;
        } else {
            head = right;
            p2 = p2.next;
        }

        ListNode p = head;
        while (p1 != null && p2 != null) {
            if (p1.value < p2.value) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }

        if (p2 != null) {
            p.next = p2;
        }

        return head;

    }

    private ListNode mid(ListNode head) {
        if (head == null || head.next == null) return head;

        //快慢指针
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}
